package com.heyqing.topic.MergeTwoLists_0021;

import java.util.Objects;

/**
 * ClassName:MergeTwoLists_0021
 * Package:com.heyqing.topic.MergeTwoLists_0021
 * Description:
 *
 * @Date:2024/5/19
 * @Author:Heyqing
 */
public class MergeTwoLists_0021 {
    /**
     * 迭代法
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoListsIterative(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode res = dummyHead;
        while (Objects.nonNull(list1) && Objects.nonNull(list2)) {
            if (list1.val <= list2.val) {
                res.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                res.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            res = res.next;
        }
        if (Objects.isNull(list1)) {
            res.next = list2;
        } else {
            res.next = list1;
        }
        return dummyHead.next;
    }

    /**
     * 递归法
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        if (Objects.isNull(list1) || Objects.isNull(list2)) {
            if (Objects.isNull(list1)) {
                return list2;
            } else {
                return list1;
            }
        }
        if (list1.val <= list2.val){
            dummyHead.val = list1.val;
            dummyHead.next  = mergeTwoListsRecursive(list1.next,list2);
        }else {
            dummyHead.val = list2.val;
            dummyHead.next = mergeTwoListsRecursive(list1,list2.next);
        }
        return dummyHead;
    }
}
